package org.example.algorithm.sliding;

import org.example.algorithm.backtracking.WordExistSolution;

import java.util.*;

public class FindSubstringSlidingSolution {

    public static void main(String[] args) {
        String s = "wordgoodgoodgoodbestword";
        String[] words = {"word","good","best","word"};
        FindSubstringSlidingSolution solution = new FindSubstringSlidingSolution();
        List<Integer> list = solution.findSubstring(s, words);
        System.out.println(list);
    }

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (words.length == 0) {
            return res;
        }
        HashMap<String, Integer> map = new HashMap<>();
        for (String word: words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        int wordLen = words[0].length();
        //注:滑动窗口起点0-wordLen-1
        for (int i=0;i<wordLen;i++) {
            int left = i;
            int right = i;
            HashMap<String, Integer> windowMap = new HashMap<>();
            int count = 0;
            while (right < s.length() - wordLen + 1) {
                String tempStr = s.substring(right, right+wordLen);
                right = right + wordLen;
                if (map.containsKey(tempStr)) {
                    int wordCount = windowMap.getOrDefault(tempStr, 0) + 1;
                    windowMap.put(tempStr, wordCount);
                    count++;
                    if (wordCount > map.get(tempStr)) {
                        //收缩窗口大小
                        int diff = wordCount - map.get(tempStr);
                        while (diff > 0) {
                            String leftStr = s.substring(left, left+wordLen);
                            left = left+wordLen;
                            if (leftStr.equals(tempStr)) {
                                diff--;
                            }
                            count--;
                            windowMap.put(leftStr, windowMap.get(leftStr)-1);
                        }
                    }
                    if (count == words.length) {
                        res.add(left);
                    }
                } else {
                    left = right;
                    windowMap.clear();
                    count = 0;
                }
            }
        }
        return res;
    }

    //逐个字符滑动 !!!部分用例依然超时
    public List<Integer> findSubstring2(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (words.length == 0) {
            return res;
        }
        HashMap<String, Integer> map = new HashMap<>();
        for (String word: words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        int len = words.length * words[0].length();
        for (int i=0;i<s.length()-len+1;i++) {
            Map<String,Integer> matchMap = new HashMap<>();
            boolean flag = true;
            for (int j=i;j<i+len;j+=words[0].length()) {
                String tempStr = s.substring(j, j+words[0].length());
                if (map.containsKey(tempStr)) {
                    if (matchMap.getOrDefault(tempStr, 0) < map.get(tempStr)) {
                        matchMap.put(tempStr, matchMap.getOrDefault(tempStr, 0) + 1);
                    } else {
                        flag = false;
                        break;
                    }
                } else {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                for (String str: matchMap.keySet()) {
                    if (!matchMap.get(str).equals(map.get(str))) {
                        flag = false;
                    }
                }
            }
            if (flag) {
                res.add(i);
            }
        }
        return res;
    }
}
